Linux Cubed Series 3: Developer Tools/Linux Cubed Series 3 - Developer Tools.iso/devel/lang/eiffel/smalleif.97/se.t/SmallEiffel/lib_show/pyramid.e

Text File | 1996-05-02 | 5.1 KB | 224 lines

-- Part of SmallEiffel -- Read DISCLAIMER file -- Copyright (C)
-- Dominique COLNET and Suzanne COLLIN -- [e-mail]
--
class PYRAMID
--
-- Solving the problem of the Pyramid for small pyramid only.
--
--| This program uses the back-tracking method.
--| Its goal is to try to fill a pyramid by making a substraction
--| between two succesive columns and to take its absolute value.
--| The result is put on the next line.
--| Example :
--|  6 14 15 3 13
--|   8 1 12 10
--|    7 11 2
--|     4  9
--|       5
--
-- See also pyramid2, which run faster than this first solution.

inherit ANY redefine print_on end;

creation
   make

feature {ANY}

   size : INTEGER;

   make is
      do
     std_output.put_string("Want to compute a small pyramid ?%N%
                %Enter a small number (> 1) : ");
     std_input.read_integer;
     size := std_input.last_integer;
     if size <= 1 then
        std_output.put_string("You feel sick ?%N");
     elseif size > biggest_one then
        std_output.put_string("Value too big for this method.%N");
     else
        !!elem.make(1,max);
        if fill_up(1) then
           std_output.put_string("Full pyramid :%N");
           print_on(std_output);
        else
           std_output.put_string("Unable to fill_up such one.%N");
        end;
     end;
      end; -- make

   max : INTEGER is
      do
         Result := (size * (size + 1)) // 2;
      end; -- max

   print_on(file: STD_FILE_WRITE) is
      local
     lig,col,nb : INTEGER;
      do
     from
        lig := 1;
        col := 1;
        nb := 0;
     until
        nb = max
     loop
        if col = 1 then
           file.put_new_line;
        end;
        file.put_integer(elem.item(indice(lig,col)));
        file.put_string(" ");
        if col = size - lig + 1 then
           col := 1 ;
           lig := lig + 1 ;
        else
           col := col + 1;
            end;
        nb := nb + 1;
     end;
     file.put_new_line;
      end; -- print_on

   belongs_to(nb : INTEGER): BOOLEAN is
      require
     nb_trop_petit: nb >= 1;
     nb_trop_grand: nb <= max;
      local
     i : INTEGER;
     trouve : BOOLEAN;
      do
     from
        i := 1;
        trouve := false;
     until
        ((i > max) or trouve)
     loop
        trouve := (nb = elem.item(i));
        i := i + 1;
     end;
     Result := trouve;
      end; -- belongs_to

   propagate (col, val_column_1: INTEGER): BOOLEAN is
      require
     val_column_1 >= 1;
     val_column_1 <= max;
     col >= 1;
     col <= size;
      local
     stop : BOOLEAN;
     lig : INTEGER;
     val : INTEGER;
      do
         if belongs_to(val_column_1) then
            Result := false ;
         else
            from
               elem.put(val_column_1,indice(1,col));
               lig := 1;
               val := val_column_1;
               stop := false;
               Result := true;
            until
               stop
            loop
               lig := lig + 1;
               if lig > col then
                  stop := true;
               else
                  val := val - elem.item(indice(lig-1,col-lig+1));
                  if val < 0 then -- valeur absolue !
                     val := - val ;
                  end;
                  if belongs_to(val) then
                     clear_column(col);
                     stop := true;
                     Result := false;
                  else
                     elem.put(val,indice(lig,col-lig+1));
                  end;
               end;
            end;
         end;
      end; -- propagate

   fill_up (col : INTEGER) : BOOLEAN is
      require
         col >= 1;
      local
         stop : BOOLEAN;
         nb : INTEGER;
      do
         if col > size then
            Result := true;
         else
            from
               stop := false;
               nb := max;
            until
               stop
            loop
               if belongs_to(nb) then
                  nb := nb - 1;
                  stop := (nb = 0);
           elseif propagate(col,nb) then
                  if  fill_up(col + 1) then
                     stop := true;
                  else
                     clear_column(col);
                     nb := nb - 1;
                     stop := (nb = 0);
                  end;
               else
                  nb := nb - 1;
                  stop := (nb = 0);
               end;
            end;
            Result := (nb > 0);
         end;
      end; -- fill_up

feature {NONE}

   elem: ARRAY[INTEGER];

   case_vide : INTEGER is 0;

   biggest_one: INTEGER is 10;

   indice (lig,col : INTEGER): INTEGER is
      require
         lig_trop_petit: lig >= 1 ;
         lig_trop_grand: lig <= size ;
         col_trop_petit: col >= 1 ;
         col_trop_grand: col <= size ;
      local
         l : INTEGER ;
      do
         l:= size - lig + 1;
     Result := max - ((l * (l + 1)) // 2) + col;
      ensure
         Result >= 1 ;
         Result <= max ;
      end; -- indice

   clear_column (col : INTEGER) is
      require
         col >= 1;
         col <= size;
      local
         lig : INTEGER;
      do
         from
            lig := 1;
         until
            lig > col
         loop
            elem.put(case_vide,indice(lig,col-lig+1));
            lig := lig + 1;
         end;
      end; -- clear_column

end -- class PYRAMID